public class SudokuSolver0104_37 {
    public void solveSudoku(char[][] board) {

        backTracking(board);

    }

    private boolean backTracking(char[][] board) {

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                if(board[i][j] == '.') {
                    for (char k = '1'; k <= '9'; k++) {
                        if(isValid(i, j, k, board)) {
                            board[i][j] = k;
                            if (backTracking(board)) return true; // 如果找到合适一组立刻返回
                            board[i][j] = '.';
                        }
                    }
                    return false; // 9个数都试完了，都不行，那么就返回false
                }
            }
        }
        return true;// 遍历完没有返回false，说明找到了合适棋盘位置了
    }

    private boolean isValid(int row, int col, char k, char[][] board){
        /**
         * 判断棋盘是否合法有如下三个维度：
         * 同行是否重复
         * 同列是否重复
         * 9宫格里是否重复
         */
        //行
        for (int l = 0; l < board.length; l++) {
            if(board[row][l] == k) return false;
        }
        //列
        for (int l = 0; l < board.length; l++) {
            if(board[l][col] == k) return false;
        }
        //九宫格
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
            for (int j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == k ) {
                    return false;
                }
            }
        }
        return true;

    }
}
